public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}


class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            //初始化为Integer.MAX_VALUE会更简便
            dp[i] = -1;
        }

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                if (dp[i - coin] >= 0 && (dp[i] == -1 || dp[i] > dp[i - coin] + 1)) {
                    dp[i] = dp[i - coin] + 1;
                }
            }
        }
        return dp[amount];
    }
}
